This invention relates to a technology of fetching data from a database, and more particularly, to a technology of fetching sorted data.
The emergence of Radio Frequency Identification (RFID) has contributed to the recent rapid increase in scale of databases that store transaction data, traceability data, and the like. The need for a way to quickly search such a large-scale database is stronger than ever.
Systems for searching a large-scale database fast include database processing systems that issue data input requests in a multiplex manner to secondary storage. The database processing systems are designed around input/output (I/O) processing to and from secondary storage which constitutes most of query processing, and shorten processing time by issuing data input requests in a multiplex manner to the secondary storage (see, for example, JP 2007-34414 A).
A database processing system disclosed in JP 2007-34414 A creates a task for fetching data each time data is required and, when the created task is executed, issues a data input request as needed. A plurality of tasks that require data input are processed in parallel, and data input requests are consequently issued in a multiplex manner to secondary storage.
In the database processing systems, tasks are processed in the order in which their data input requests are fulfilled. The database processing systems are characterized in that, with data input requests issued in a multiplex manner to secondary storage, the order in which the data input requests are fulfilled usually varies each time processing is executed, thus varying the order in which query results are generated each time. Unless a particular order in which query results are output is specified, it can be confirmed that query results are output in a different order each time processing is executed.
Another way to accomplish fast search is a technology developed around sort processing of query processing. Sort processing is used to arrange query results in a specific output order, or as preprocessing for aggregation of query results. The search speed enhancing technology developed around sort processing is important as well because a larger database scale means increased sort processing cost.
Sort cancel is a known search speed enhancing technology developed around sort processing. Database processing systems commonly have an access method which reads data in a specific order. For instance, in the case where an index is used in order to retrieve data with a few data input requests, data can be accessed in the order of index keys. In the case of a clustered table, data in the table can be accessed in the order of cluster keys. These utilize a data reading order ensured by the access method, to thereby avoid subsequent sort processing. Another advantage of sort cancel is that, with sort processing excluded from the search operation, a query result can be output before the reading of all data to be read is finished. This is particularly effective for top-k query processing in which only the first k hits are retrieved. Details of sort cancel are described in Hector Garcia-Molina, “Database System Implementation”, Prentice Hall, 1999, pp. 258, 417-418.